Search for: All records

An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}). 

Let L be a set of n axis-parallel lines in R3. We are are interested in partitions of R3 by a set H of three planes such that each open cell in the arrangement A(H) is intersected by as few lines from L as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. * There are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H)  that intersects at least ⌊n/3⌋ - 1 ≈ n/3 lines. * If we require the splitting planes to be axis-parallel, then there are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least (3/2) ⌊n/3⌋ - 1 ≈ (1/3 + 1/24) n lines. Furthermore, for any set L of n axis-parallel lines, there exists a set H of three axis-parallel splitting planes such that each open cell in A(H) intersects at most (7/18) n = (1/3 + 1/18) n lines. * For any set L of n axis-parallel lines, there exists a set H of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in A(H) intersects at most ⌈5/12 n⌉ ≈ (1/3 + 1/12) n lines. 

For an $$r$$-uniform hypergraph $$H$$, let $$\nu^{(m)}(H)$$ denote the maximum size of a set $$M$$ of edges in $$H$$ such that every two edges in $$M$$ intersect in less than $$m$$ vertices, and let $$\tau^{(m)}(H)$$ denote the minimum size of a collection $$C$$ of $$m$$-sets of vertices such that every edge in $$H$$ contains an element of $$C$$. The fractional analogues of these parameters are denoted by $$\nu^{*(m)}(H)$$ and $$\tau^{*(m)}(H)$$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$$. In this paper we prove bounds on the ratio between the parameters $$\tau^{(m)}$$ and $$\nu^{(m)}$$, and their fractional analogues. Our main result is that, for every $$r$$-uniform hypergraph~$$H$$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $$r-1$.We also prove that, for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$$, where the Turán number $$\operatorname{ex}_r(n, k)$$ is the maximum number of edges in an $$r$$-uniform hypergraph on $$n$$ vertices that does not contain a copy of the complete $$r$$-uniform hypergraph on $$k$$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$. 

Abstract A bipartite graph $$H = \left (V_1, V_2; E \right )$$ with $$\lvert V_1\rvert + \lvert V_2\rvert = n$$ is semilinear if $$V_i \subseteq \mathbb {R}^{d_i}$$ for some $$d_i$$ and the edge relation E consists of the pairs of points $$(x_1, x_2) \in V_1 \times V_2$$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $$d_1 + d_2$$ variables for some s . We show that for a fixed k , the number of edges in a $$K_{k,k}$$ -free semilinear H is almost linear in n , namely $$\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ for any $$\varepsilon> 0$$ ; and more generally, $$\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$$ for a $$K_{k, \dotsc ,k}$$ -free semilinear r -partite r -uniform hypergraph. As an application, we obtain the following incidence bound: given $$n_1$$ points and $$n_2$$ open boxes with axis-parallel sides in $$\mathbb {R}^d$$ such that their incidence graph is $$K_{k,k}$$ -free, there can be at most $$O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o -minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).